This invention relates generally to computer systems and more specifically to the memory portions of such systems.
One of the major trends in computer science of the last decade has been the increasing popularity of the "object-oriented" paradigm. While there is little consensus regarding the meaning of this term, any object-oriented system must be concerned with the allocation and maintenance of storage for "objects" where an "object" is data that share a particular attribute and occupy a contiguous region of memory. Objects are not permitted to overlap. "Live" objects are those needed in the computational process currently being performed by a computer system.
If all objects in a system are permanent, then there is no concern about memory management. The space assigned to each object at system startup need never be reclaimed. In most real systems, however, live objects have varying lifetimes that cannot be predicted in advance. In such systems, some method of recognizing expired ("dead") objects and evicting them from memory is necessary if memory resources are to be conserved.
"Garbage" is a term of art in computer technology which refers to data stored in computer system memory that is no longer being used in the performance of an application program. Garbage collection is the process of locating data in dynamically-allocated memory that is no longer being used and reclaiming the memory to satisfy future allocation requests. Since garbage collection greatly reduces low-level programming detail, it offers the potential of significant programmer productivity gains. By freeing programmers from this low-level detail, garbage collection encourages programmers and system designers to dedicate their intellectual efforts to higher-level pursuits, such as the design of fundamental algorithms, user interfaces, and general program functionality. Also, by eliminating many low-level programming concerns, garbage collection reduces the likelihood of programming errors. And finally, dynamic memory management based on copying-types of garbage-collection algorithms are capable of delivering much higher storage throughput than explicit allocation and deallocation, reference-count storage reclamation, and even stack allocation. Together these benefits of garbage collection combine to offer improved software functionality and reliability for lower development costs.
Traditional garbage collectors work by periodically halting execution of system programs in order to traverse all of memory in search of memory regions that are no longer in use. Traditional garbage collectors have a number of major shortcomings: (1) storage throughput in terms of rates of allocation and deallocation of objects is generally much lower than, for example, stack allocation; (2) the times required to allocate memory are only very loosely bounded--the bounds on allocation times are not tight enough to allow reliable programming of highly-interactive or real-time systems such as mouse tracking, interactive multimedia device control, virtual reality systems, and reactive robot control; and (3) in incremental garbage collection systems, the performance penalties associated with memory reads and writes are so high that overall system performance may be unacceptably slow.
Traditional garbage collection systems are incompatible with real-time systems because of their stop-and-wait behavior. Real-time garbage collectors work by dividing the labor of garbage collection into many small steps so that system programs are infrequently halted for the purpose of collecting garbage. Software prototypes of real-time garbage collection algorithms demonstrate the feasibility of the real-time algorithms but exhibit much poorer throughput than traditional garbage collection algorithms. By dedicating hardware to the task of garbage collection, both real-time response and high storage throughput are possible.
A number of incremental garbage collection techniques have been proposed. Some of these are capable of guaranteeing upper bounds on the times required to allocate a unit of memory and to read or write previously allocated memory cells. All of the incremental garbage collection algorithms require frequent synchronization between the application processor and the garbage collector. Depending on the algorithm, this synchronization generally consists of one or more extra instructions executed on every fetch or store that accesses the garbage-collected heap. In detailed performance analysis of these systems, the overhead of synchronizing on writes ranges from 3 to 24 percent of total execution time in one study, and synchronizing on reads was found to more than double execution time in a different study. Furthermore, all garbage collectors occasionally suspend execution of the application while the garbage collector completes certain uninterruptable activities.
A real-time garbage collector must honor a certain upper bound on the duration of time during which it might suspend execution of the application process. The tightest bound currently available on the time applications must wait for garbage collection based on using stock hardware is 500 microseconds for applications that are somewhat restricted in their use of dynamic memory. More general garbage collection systems promise looser bounds ranging from several to several hundred milliseconds. Suspending execution of the application process for time periods such as these is unacceptable for many real-time system applications.